#include "stdafx.h"
#include "Game.h"
#include "windows.h"
#include "atlstr.h"
using namespace std;
/*
the global array MapData records the initial map data of the game
1 means no barrier
0 means it is a barrier
*/

int mapData[MAP_HEIGHT * MAP_WIDTH] = 
{
#ifdef MAP_1
	1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,
	1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,
	1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,
	1,1,1,0,0,1,1,1,1,1,0,1,1,1,1,
	1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,
	1,1,1,1,1,1,1,0,0,0,1,1,1,1,0,
	0,1,1,1,1,1,1,0,0,1,1,1,1,0,0,
	0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,
	0,0,1,1,1,0,0,1,1,1,0,1,0,0,0,
	0,0,0,1,0,0,0,1,1,1,0,1,1,1,1,
	0,0,0,0,0,1,1,1,1,1,0,1,1,1,0,


#else
#ifdef MAP_2
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

#else
#ifdef MAP_3
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,


#endif // MAP_3

#endif // MAP_2

#endif // MAP_1



};

static int GetStep(int Position, int *pStepNo, const int * outputMap);
static int _Inner_CreatePoint(int x,int y);
static int _Inner_GetRow(int m);
static int _Inner_GetCol(int m);


int GetX(int m)
{
	return _Inner_GetCol (m);
}
int GetY(int m)
{
	return MAP_HEIGHT - 1 - _Inner_GetRow (m);
}


int _Inner_GetRow(int x)
{
	return x/MAP_WIDTH;
}
int _Inner_GetCol(int x)
{
	return x%MAP_WIDTH;
}
int _Inner_CreatePoint(int x,int y)
{
	return y*MAP_WIDTH + x;
}

int CreatePoint(int x,int y)
{
	return _Inner_CreatePoint (x,MAP_HEIGHT-1-y);
}

int GetNearPoint(int pos,int type)
{
	switch (type)
	{
	case LEFT_TOP:
		if (_Inner_GetRow (pos) == 0 || (_Inner_GetRow (pos) % 2 ==1 && _Inner_GetCol (pos)==0))
		{
			return -1;
		}
		return pos - MAP_WIDTH - _Inner_GetRow (pos)%2;
		break;
	case RIGHT_TOP:
		if (_Inner_GetRow (pos) == 0 || (_Inner_GetRow (pos)%2==0 && _Inner_GetCol (pos) == MAP_WIDTH - 1))
		{
			return -1;
		}
		return pos - MAP_WIDTH + 1- _Inner_GetRow (pos)%2;
		break;
	case RIGHT:
		if (_Inner_GetCol (pos) == MAP_WIDTH - 1)
		{
			return -1;
		}
		return pos + 1;
		break;
	case RIGHT_BOTTOM:
		if (_Inner_GetRow (pos) == MAP_HEIGHT - 1 || (_Inner_GetRow (pos)%2==0&&_Inner_GetCol (pos)== MAP_WIDTH - 1))
		{
			return -1;
		}
		return pos + MAP_WIDTH + 1 - _Inner_GetRow (pos)%2;
		break;
	case LEFT_BOTTOM:
		if (_Inner_GetRow (pos) == MAP_HEIGHT - 1 ||(_Inner_GetRow (pos) % 2 ==1 && _Inner_GetCol (pos)==0))
		{
			return -1;
		}
		return pos + MAP_WIDTH - _Inner_GetRow (pos)%2;
		break;
	case LEFT:
		if (_Inner_GetCol (pos) == 0)
		{
			return -1;
		}
		return pos - 1;
		break;
	}
	return -1;
}


void GetCanWalk(int * MapData,int  Pos_Start,int * outputMap,int Max_step)
{
	
	queue<int>Que;
	int StepNo = 1,Position,CurrentPos;
	outputMap[Pos_Start] = StepNo;
	Que.push (Pos_Start);
	for (;;)
	{
		if (Que.empty ())
		{
			return;
		}
		CurrentPos = Que.front ();
		Que.pop ();
		StepNo = outputMap[CurrentPos];
		if (StepNo > Max_step)
		{
			continue;
		}
		for (int i = 0;i < DIRECTION_COUNT;i++)
		{
			Position = GetNearPoint (CurrentPos,i);
			if (Position>=0&&MapData[Position] != 0)
			{
				if (outputMap[Position] == 0 ||
					outputMap[Position] > StepNo +1)
				{
					outputMap[Position] = StepNo+1;
					Que.push(Position);
				}

			}
		}
	}
}

void GetCanWalk2(int * MapData,int  Pos_Start,int * outputMap,int Max_step)
{

	queue<int>Que;
	int StepNo = 1,Position,CurrentPos;
	outputMap[Pos_Start] = StepNo;
	Que.push (Pos_Start);
	for (;;)
	{
		if (Que.empty ())
		{
			return;
		}
		CurrentPos = Que.front ();
		Que.pop ();
		StepNo = outputMap[CurrentPos];
		if (StepNo > Max_step)
		{
			continue;
		}
		for (int i = 0;i < DIRECTION_COUNT;i++)
		{
			Position = GetNearPoint (CurrentPos,i);
			if (Position>=0&&MapData[Position] != 0)
			{
				if (outputMap[Position] == 0 ||
					outputMap[Position] > StepNo +1)
				{
					int bRighPosHasSomething = 
						GetNearPoint (Position,RIGHT);//check the right pos
					if (bRighPosHasSomething >=0 &&
						MapData[bRighPosHasSomething]!=0)
					{
						outputMap[Position] = StepNo+1;
						Que.push(Position);
					}
					
				}

			}
		}
	}
}

void GetCanFly(int * MapData,int Pos_Start,int * outputMap,int Max_step)
{
	int MapDataTemp[MAP_SIZE];
	memcpy(MapDataTemp,MapData,MAP_SIZE*sizeof(4));
	for (int i = 0;i < MAP_SIZE;i++)
	{
		MapData[i] = 1;
	}

	GetCanWalk (MapData,Pos_Start,outputMap,Max_step);

	for (int i = 0;i < MAP_SIZE;i++)
	{
		if (MapDataTemp[i]== 0 )
		{
			outputMap[i] = 0;
		}
	}
	memcpy(MapData,MapDataTemp,MAP_SIZE*sizeof(int));
}

void GetCanFly2(int * MapData,int Pos_Start,int * outputMap,int Max_step)
{
	int MapDataTemp[MAP_SIZE];
	memcpy(MapDataTemp,MapData,MAP_SIZE*sizeof(4));
	for (int i = 0;i < MAP_SIZE;i++)
	{
		MapData[i] = 1;
	}

	GetCanWalk (MapData,Pos_Start,outputMap,Max_step);

	for (int i = 0;i < MAP_SIZE;i++)
	{
		if (MapDataTemp[i]== 0 )
		{
			outputMap[i] = 0;
			continue;
		}
		int pt = GetNearPoint (i,RIGHT);
		if (pt < 0)
		{
			outputMap[i] = 0;
			continue;
		}
		if (MapDataTemp[pt] == 0)
		{
			outputMap[i] = 0;
			continue;
		}
	}
	memcpy(MapData,MapDataTemp,MAP_SIZE*sizeof(int));
}

int GetWalkRoute(int * MapData,int StartPos, int TargetPos,const int * outputMap,int * PrintMap)
{
	if (outputMap[StartPos]*outputMap[TargetPos] == 0)
	{
		return -1;
	}
	int Path[MAP_SIZE] = {0};
	int Step = outputMap[TargetPos];
	int index = 0;
	int Pos = TargetPos;
	Path[index++] = Pos;
	do 
	{
		Pos = GetStep(Pos, &Step,outputMap);
		if (Pos != -1)
		{
			Path[index++] = Pos;
			if (Pos == StartPos)
			{
				break;
			}
		}
		else
			break;

	} while(true);

	int ret = index;

	int iPos;
	for (int loop = 0; loop < index; loop++)
	{
		iPos = Path[loop];
		PrintMap[iPos] = 1;
	}
	return ret;
}

int GetFlyRoute(int * MapData,int StartPos, int TargetPos,int * Path)
{
	int cx = _Inner_GetRow (StartPos) - _Inner_GetRow (TargetPos);
	cx = cx>0?cx:-cx;
	int cy = _Inner_GetCol (StartPos) - _Inner_GetCol (TargetPos);
	cy = cy>0?cy:-cy;
	int max_step = cx + cy +2;
	int MapDataTemp[MAP_SIZE];
	memcpy(MapDataTemp,MapData,MAP_SIZE*sizeof(4));
	for (int i = 0;i < MAP_SIZE;i++)
	{
		MapData[i] = 1;
	}
	int outputMap[MAP_SIZE]={0};
	GetCanWalk (MapData,StartPos,outputMap,max_step);
	int ret  = GetWalkRoute (MapData,StartPos,TargetPos,outputMap,Path);

	memcpy(MapData,MapDataTemp,MAP_SIZE*sizeof(int));
	return ret;
}

int GetStep(int Position, int *pStepNo,const int * outputMap)
{
	for (int i = 0;i < DIRECTION_COUNT;i++)
	{
		int pos = GetNearPoint (Position,i);
		if (pos>=0&&outputMap[pos] != 0 && outputMap[pos] < *pStepNo)
		{
			*pStepNo = outputMap[pos];
			return pos;
		}
	}
	return -1;
}

void PrintOutMap(int * pdata)
{
	printf ("    ");
	for (int i = 0;i < MAP_WIDTH;i++)
	{
		printf ("%2d ",i);
	}
	printf ("\n");
	for (int i = 0;i < MAP_HEIGHT;i++)
	{
		printf ("%2d ",MAP_HEIGHT-1-i);
		if (i%2==0)
		{
			printf (" ");
		}
		for (int j = 0;j < MAP_WIDTH;j++)
		{
			int dis = pdata[i*MAP_WIDTH + j];
			if (dis == 0)
			{
				printf (" **");
			}
			else
			{
				printf(" %02d", dis);
			}
		} 
		printf ("\n");
	}
	printf ("------------------------------------------\n");
}



int main()
{
	/**
	The Unit can only walk and it's small:
	*/
	//int outPutMap[MAP_SIZE]={0};//this array is used to receive the boundary a unit can walk
	//int Pos_Start = CreatePoint(0,10);
	//PrintOutMap (mapData);//Output the initial map:
	//GetCanWalk(mapData,Pos_Start,outPutMap,70);
	//PrintOutMap (outPutMap);//out put the boundary this unit can walk
	//int Path[MAP_SIZE] = {0};//Path is the last moving routing
	//GetWalkRoute(mapData,Pos_Start, CreatePoint (9,0),outPutMap,Path);
	//PrintOutMap(Path);//out put the route that unit choose to walk


	/**
	The Unit can fly:
	*/
	//int outPutMap[MAP_SIZE]={0};
	//int Pos_Start = CreatePoint(0,10);
	//PrintOutMap (mapData);//Output the initial map:
	//GetCanFly(mapData,Pos_Start,outPutMap,17);//this array is used to receive the boundary a unit can fly
	//PrintOutMap (outPutMap);//out put the boundary this unit can fly
	//int Path[MAP_SIZE] = {0};//Path is the last moving routing
	//GetFlyRoute(mapData,Pos_Start, CreatePoint(11,6),Path);
	//PrintOutMap(Path);
	
	/**
	The Unit can only walk and it's Large:
	*/
	//int outPutMap[MAP_SIZE]={0};//this array is used to receive the boundary a unit can walk
	//int Pos_Start = CreatePoint(0,10);
	//PrintOutMap (mapData);//Output the initial map:
	//GetCanWalk2(mapData,Pos_Start,outPutMap,70);
	//PrintOutMap (outPutMap);//out put the boundary this unit can walk
	//int Path[MAP_SIZE] = {0};//Path is the last moving routing
	//GetWalkRoute(mapData,Pos_Start, CreatePoint (8,0),outPutMap,Path);
	//PrintOutMap(Path);//out put the route that unit choose to walk

	/**
	The Unit can fly and it's Large:
	*/
	//int outPutMap[MAP_SIZE]={0};
	//int Pos_Start = CreatePoint(0,10);
	//PrintOutMap (mapData);//Output the initial map:
	//GetCanFly2(mapData,Pos_Start,outPutMap,17);//this array is used to receive the boundary a unit can fly
	//PrintOutMap (outPutMap);//out put the boundary this unit can fly
	//int Path[MAP_SIZE] = {0};//Path is the last moving routing
	//GetFlyRoute(mapData,Pos_Start, CreatePoint(11,6),Path);
	//PrintOutMap(Path);
	return 0;
}

